﻿#define _CRT_SECURE_NO_WARNINGS  1
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;

//1137.第N个泰波那契数
class Solution {
public:
    int tribonacci(int n)
    {
        vector<int> dp(n + 1); //要到下标为N的数
        if (n == 0) return 0;  // n为0不能访问dp[1]和dp[2]
        if (n == 1) return 1;// n为1不能访问dp[2]
        dp[0] = 0, dp[1] = 1,dp[2]=1;
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; // 0 1 2
        }

        return dp[n];
    }
};



//08.01.三步问题
class Solution2 {
public:
    int waysToStep(int n)
    {
        vector<int> dp(n + 1);
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        dp[1] = 1; dp[2] = 2, dp[3] = 4;
        int tmp = 1e9 + 7;

        for (int i = 4; i <= n; i++)
        {
            dp[i] = ((dp[i - 1] + dp[i - 3]) % tmp + dp[i - 2]) % tmp;
        }
        return dp[n];
    }
};



// 746.使用最小花费爬楼梯
class Solution3 {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        int n = cost.size();
        vector<int> dp(n + 1);
        if (n == 0 || n == 1) return 0;
        dp[0] = dp[1] = 0;  //从0和1开始，没有花费       


        for (int i = 2; i <= n; i++)
        {
            dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
        }

        return dp[n];
    }
};



//91.解码方法
class Solution4 {
public:
    int numDecodings(string s)
    {
        int n = s.size();
        vector<int> dp(n); //   dp[i] -> 0-n的解码方式总和
        dp[0] = s[0] != '0';  

        if (n == 1)
        {
            return dp[0];
        }

        if (s[1] >= '1' && s[1] <= ' 9')   //单独解码
        {
            dp[1] += dp[0];
        }
        if ((s[0] - '0') * 10 + (s[1] - '0') >= 10 && (s[0] - '0') * 10 + (s[1] - '0') <= 26)  //与s[i-1]解码
        {
            dp[1] += 1;
        }


        for (int i = 2; i < n; i++)
        {
            if (s[i] >= '1' && s[i] <= '9') dp[i] += dp[i - 1]; //单独解码 dp[i]=dp[i-1]
            if ((s[i - 1] - '0') * 10 + (s[i] - '0') >= 10 && (s[i - 1] - '0') * 10 + (s[i] - '0') <= 26) dp[i] += dp[i - 2];
            //组合解码 dp[i]=dp[i-2]
        }

        return dp[n - 1];

    }



};

class solution4 {
public:
    int numDecodings(string s)
    {
        int n = s.size();
        vector<int> dp(n + 1); // 0-n的解码方式总和
        dp[0] = 1;
        dp[1] = s[0] != '0';


        for (int i = 2; i <= n; i++)
        {
            if (s[i - 1] >= '1' && s[i - 1] <= '9') dp[i] += dp[i - 1];
            if ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') >= 10 && (s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26) dp[i] += dp[i - 2];

        }

        return dp[n];

    }



};

//62.不同路径
class Solution5 {
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1)); //多给一行一列，全部初始化成0
        dp[1][0] = 1;

        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m][n];
    }
};


//63.不同路径II
class Solution6 {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[1][0] = 1;
        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                if (obstacleGrid[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                else
                    dp[i][j] = 0;
            }
        }

        return dp[m][n];
    }
};


//剑指Offer 47.礼物的最⼤价值
class Solution7 {
public:
    int jewelleryValue(vector<vector<int>>& frame)
    {
        int m = frame.size();
        int n = frame[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }


        return dp[m][n];
    }
};

//931.下降路径最⼩和
class Solution8 {
public:
    int minFallingPathSum(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        for (int i = 0; i < n + 2; i++) dp[0][i] = 0;

        for (int i = 1; i < n + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        int ret = INT_MAX;
        for (int i = 0; i < n + 2; i++)
        {
            ret = min(ret, dp[n][i]);
        }
        return ret;
    }


};

//64.最⼩路径和
class Solution9{
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[1][0] = 0;


        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }

        return dp[m][n];
    }
};


//174.地下城游戏
class Solution10 {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon)
    {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;

        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }

        return dp[0][0];
    }
};

//⾯试题17.16.按摩师
class Solution11 {
public:
    int massage(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> f(n);
        vector<int> g(n);
        f[0] = nums[0], g[0] = 0;
        for (int i = 1; i < n; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};


//213.打家劫舍II
class Solution12 {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        vector<int> f(n);  //偷当前位子
        vector<int> g(n);  //不偷当前位子
        f[0] = g[0] = 0;
        int i;
        // [0-n-2]  [1-n-1]
        for (int i = 1; i <= n - 1; i++)   //不偷0位置
        {


            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        int t1 = max(f[n - 1], g[n - 1]);
        f[0] = f[1] = nums[0]; g[1] = 0; g[0] = 0;
        for (int i = 1; i <= n - 2; i++)   //偷0位子
        {

            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        int t2 = max(f[n - 2], g[n - 2]);
        return max(t1, t2);
    }
};



//740.删除并获得点数
class Solution13 {
public:
    int deleteAndEarn(vector<int>& nums)
    {
        int n = nums.size();
        int maxs = nums[0];
        for (auto ch : nums)
        {
            if (ch > maxs)
                maxs = ch;
        }
        vector<int> news(maxs + 1);
        for (auto ch : nums)
        {

            news[ch] += ch;
        }

        vector<int> fp(maxs + 1 + 1);
        auto gp = fp;
        fp[0] = news[0]; gp[0] = 0;
        for (int i = 1; i < maxs + 1; i++)
        {
            fp[i] = gp[i - 1] + news[i];
            gp[i] = max(fp[i - 1], gp[i - 1]);
        }

        return max(fp[maxs], gp[maxs]);
    }

  
};

//剑指offer 91.粉刷房⼦
class Solution14_1
{
public:
    int minCost(vector<vector<int>>& costs)
    {
        //0--红
        //1--蓝
        //2--绿
        int m = costs.size();
        int n = costs[0].size();
        vector<vector<int>> f(m + 1, vector<int>(n));
        auto g = f;
        //for (int j = 0; j < n; j++) f[0][j] = costs[0][j];
        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (j == 0)
                {
                    f[i][j] = min(f[i - 1][j + 1], f[i - 1][j + 2])+costs[i-1][j];
                }
                else if (j == 1)
                {
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j + 1]) + costs[i - 1][j];
                    g[i][j] = min(f[i - 1][j], f[i - 1][j + 1]);
                }
                else if (j == 2)
                {
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j - 2]) + costs[i - 1][j];
                    g[i][j] = min(f[i][j - 1], f[i][j - 2]);
                }
            }

        }
        return min(f[m][n-1], g[m][n-1]);

    }
};


class Solution14_2
{
public:
    int minCost(vector<vector<int>>& costs)
    {
        //0--红
       //1--蓝
       //2--绿
        int m = costs.size();
        int n = costs[0].size();
        vector<vector<int>> f(m + 1, vector<int>(n));
        auto g = f;
        for (int i = 1; i < m + 1; i++)
        {
            f[i][0] = min(f[i - 1][1], f[i - 1][2]) + costs[i - 1][0];

            f[i][1] = min(f[i - 1][0], f[i - 1][2]) + costs[i - 1][1];
            g[i][1] = min(f[i - 1][0], f[i - 1][2]);

            f[i][2] = min(f[i - 1][1], f[i - 1][0]) + costs[i - 1][2];
            g[i][2] = min(f[i][1], f[i][0]);


        }
        return min(f[m][n - 1], g[m][n - 1]);

    }
};


//309.最佳买卖股票时机含冷冻期
class Solution15 {
public:
    int maxProfit(vector<int>& prices)
    {
        int m = prices.size();
        vector<vector<int>> dp(m + 1, vector<int>(3)); 
        //0:解冻
        //1:有股票
        //2.冷冻期
        dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0;

        for (int i = 1; i < m + 1; i++)
        {
            dp[i][0] = max(dp[i - 1][2], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
            dp[i][2] = dp[i - 1][1] + prices[i - 1];
        }

        return max(dp[m][0], max(dp[m][1], dp[m][2]));
    }
};


//714.买卖股票的最佳时机含⼿续费
class Solution16_1 {
public:
    int maxProfit(vector<int>& prices, int fee)
    {
        int m = prices.size();
        vector<vector<int>> dp(m + 1, vector<int>(2));
        dp[0][0] = -prices[0]; dp[0][1] = 0;

        for (int i = 1; i < m + 1; i++)
        {
            dp[i][0] = max(dp[i - 1][1] - prices[i - 1], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][0] + prices[i - 1] - fee, dp[i - 1][1]);

        }

        return max(dp[m][0], dp[m][1]);
    }
};


class Solution16_2{
public:
    int maxProfit(vector<int>& prices, int fee)
    {
        
        int n = prices.size();
        vector<int> f(n);
        auto g = f;
        f[0] = -prices[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
       return max(f[n - 1], g[n - 1]);

    }
};

//123.买卖股票的最佳时机III
class Solution17 {
public:
    int maxProfit(vector<int>& prices)
    {
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 0; i < prices.size(); i++)
        {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};


//188.买卖股票的最佳时机IV
class Solution18 {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<int> buy(k + 1, INT_MIN / 2);
        vector<int> sell(k + 1, 0);
        for (int i = 0; i < prices.size(); i++)
        {
            for (int j = 1; j <= k; j++)
            {
                buy[j] = max(buy[j], sell[j - 1] - prices[i]);
                sell[j] = max(sell[j], buy[j] + prices[i]);
            }
        }
        return sell[k];
    }
};

//53.最⼤⼦数组和
class Solution19_1 {
public:
    int maxSubArray(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n + 1);
        dp[0] = 0;
        int ret = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

class Solution19_2 {
public:
    int maxSubArray(vector<int>& nums)
    {
        int n = nums.size();
        int nownumber = 0;
        int target = INT_MIN;
        for (int left = 0, right = 0; right < n;)
        {
            nownumber += nums[right];
            while (nownumber < nums[right])
            {
                nownumber -= nums[left];
                left++;
            }
            right++;
            if (nownumber > target)
            {
                target = nownumber;
            }
        }
        return target;
    }
};

//918.环形⼦数组的最⼤和
class Solution20 {
public:
    int maxSubarraySumCircular(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n);
        auto g = f;
        int fmax = nums[0], gmin = nums[0], sum = 0;
        for (auto ch : nums) sum += ch;
        f[0] = nums[0], g[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = max(nums[i], f[i - 1] + nums[i]);
            fmax = max(fmax, f[i]);
            g[i] = min(nums[i], g[i - 1] + nums[i]);
            gmin = min(gmin, g[i]);
        }

        return sum == gmin ? fmax : max(fmax, sum - gmin);
    }
};

//152.乘积最⼤⼦数组
class Solution21 {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1); //最大子数组----正数
        auto g = f;  //最小子数组----负数
        int ret = INT_MIN;
        f[0] = g[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            f[i] = max(max(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]);
            g[i] = min(min(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]);
            ret = max(f[i], ret);
        }
        return ret;
    }
};

//1567.乘积为正数的最⻓⼦数组⻓度
class Solution22 {
public:
    int getMaxLen(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n);
        auto g = f;
        if (nums[0] > 0) f[0] = 1;
        else if (nums[0] < 0) g[0] = 1;
        int ret = f[0];
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }
            else if (nums[i] < 0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(ret, f[i]);
        }

        return  ret;
    }
};



//413.等差数列划分
class Solution23 {
public:
    int numberOfArithmeticSlices(vector<int>& nums)
    {
        int n = nums.size();
        if (n < 3) return 0;
        vector<int> dp(n);
        int sum = 0;
        for (int i = 2; i < n; i++)
        {
            dp[i] = nums[i] + nums[i - 2] == 2 * nums[i - 1] ? dp[i - 1] + 1 : 0;
            sum += dp[i];
        }

        return sum;

    }
};

//978.最⻓湍流⼦数组
class Solution24 {
public:
    int maxTurbulenceSize(vector<int>& arr)
    {
        int n = arr.size();
        vector<int> f(n); //上升状态下，最长湍流子数组长度
        auto g = f;//下降状态下，最长湍流子数组长度
        if (n == 1) return 1;
        f[0] = g[0] = 1;
        int ret = INT_MIN;
        for (int i = 1; i < n; i++)
        {
            if (arr[i] > arr[i - 1])
            {
                g[i] = f[i - 1] + 1;
                f[i] = 1;
            }
            else if (arr[i] < arr[i - 1])
            {
                f[i] = g[i - 1] + 1;
                g[i] = 1;
            }
            else if (arr[i] == arr[i - 1])
            {
                f[i] = g[i] = 1;
            }
            ret = max(max(ret, g[i]), f[i]);
        }
        return ret;
    }
};


int main()
{
    Solution16_1 s;
    vector<int> v{ 3,3,5,0,0,3,1,4 };

    cout<<s.maxProfit(v,2);
    return 0;
}


